1. Field of the Invention
The present invention relates to a device for fetching data stored in a memory and a method thereof. More specifically, the present invention relates to a pre-fetch controller for efficiently pre-fetching data stored in a memory and a method thereof.
2. Description of the Prior Art
A computer generally contains a calculating unit (for example, a CPU), and a storage unit (for example, a DRAM) where the data and instructions are stored, and the calculating unit fetches the required data and instructions from the storage unit to perform a predetermined logic operation. In addition, the calculating unit also stores the output of the predetermined logic operation back into the storage unit. As chip fabrication technology advances, CPU clock speeds are increasing more rapidly than DRAM speeds, so the clock speed of the CPU is generally higher than that of the DRAM, i.e., the data processing speed of the CPU is higher than that of the DRAM. After the CPU sends out a fetch instruction to fetch a given piece of data from the DRAM, the CPU must wait until the DRAM reads and sends back that data to the CPU. Consequently, the operating efficiency of the CPU is lowered due to the delay caused by the DRAM. To alleviate this, a cache is introduced to reduce delay. Comparing with the prior art DRAM, the cache (for example, SRAM) has a higher speed of data access. The storage capacity of the cache (for example, L2 cache in a CPU) in a computer is usually much smaller than that of the DRAM because the high cost.
FIG. 1 shows the block diagram of a prior art data processing system 10. The data processing system 10 contains a cache 12, a pre-fetch controller 14, a memory controller 16, and a DRAM 18. As mentioned above, the data access speed of the cache 12 is higher than that of the DRAM 18; therefore, when the CPU is performing a logic operation, the operating efficiency of the CPU can be increased if the CPU can get the required data directly from the cache 12. To increase the efficiency of the CPU, the pre-fetch controller 14 predicts that DATAa, DATAb, and DATAc in the DRAM 18 will be required when the CPU is performing a given logic operation, and then tells the memory controller 16 to read DATAa, DATAb, and DATAc from the DRAM 18 and send them to the cache. Accordingly, when the cache 12 is subsequently searched by the CPU, if DATAa, DATAb, and DATAc are the required data when the CPU is performing the logic operation, then a “cache hit” occurs for each of DATAa, DATAb, and DATAc, and the CPU can access DATAa, DATAb, and DATAc directly from the cache 12 to perform the logic operation. However, generally, the prediction of the pre-fetch controller 14 does not exactly match the data required during the logic operation. That is, the pre-fetch controller 14 predicts that DATAa, DATAb, and DATAc will be required during the logic operation, but DATAa, DATAb, and DATAd stored in the DRAM 18 are actually required instead. Thus, when the CPU executes the logic operation, cache hits occur when the CPU searches for DATAa and DATAb in the cache 12, and so the CPU accesses DATAa and DATAb successfully from the cache 12. However, a “cache miss” occurs when the CPU searches for DATAd in the cache 12, and so the CPU must fetch DATAd from the DRAM 18 via the memory controller 16, and DATAd will then be stored in the cache 12 and transmitted to the CPU at the same time. In short, the CPU must wait until it receives DATAd from the DRAM 18, and only thereafter can the logic operation execution continue.
In conclusion, because DATAc is not the required, the pre-fetch controller 14 wastes the bandwidth between the memory controller 16 and the DRAM 18 when it pre-fetches DATAc from the DRAM 18. As a result, if the accuracy of the pre-fetch controller 14 is too low, i.e., if “cache miss” occurs too frequently when the CPU is searching the cache 12 for required data, then the pre-fetch action will seriously lower the efficiency of the computer.